1. Field of the Invention
The present invention relates to condition detection in asynchronous pipelines.
2. Discussion of Prior Art
A pipeline is a mechanism used in computer architecture for speeding up system throughput. It is analogous to a production line, where the product (data) flows through a series of stages (circuits) in each of which an operation is performed to process the product (data). The use of a pipeline mechanism does not speed up the time taken for an individual element of data to traverse the pipeline (the latency) but rather increases the number of elements of data processed in a given time (the throughput). This is achieved because the operations comprising the pipeline can be kept simple and each can start processing a subsequent element as soon as the current element has passed through that stage. A non-pipelined implementation of the same set of operations requires that all processing is complete on any one of a number of elements before further elements can be processed.
Computer pipeline systems are conventionally synchronous. In such systems, several stages operate in "lockstep". A global clock signal is asserted when all the stages have completed operation and data is transferred to subsequent stages. This gives a simple structure which is easy both to model and to analyze. The clock period of the pipeline is, of course, limited to a minimum of the time taken for the slowest pipeline stage to complete its processing. The clock frequency thus derived determines the throughput of the pipeline. The pipeline latency is the clock period multiplied by the number of pipeline stages, which will generally be somewhat greater than the processing time for the same logic without pipelining.
For example, in a synchronous pipeline comprising three elements having respective clock frequencies of 50 MHz, 10 MHz and 30 MHz when operating in isolation, the maximum clock frequency of the system is limited to 10 MHz if all the elements are to function correctly. This frequency determines the pipeline throughput. Even if the slowest element is not in use, due for example to the pipeline having been flushed and not yet fully refilled, the system is synchronised to the global clock and thus cannot run any faster.
In an asynchronous system the basic speed limitation still applies, that is in the case outlined above the system would naturally adopt a throughput rate of 10 MHz given that this is the speed of the slowest element. However each element is free operate at its own rate and in an operation where the slowest unit was not in use the throughput would automatically rise to that of the next slowest element, that is 30 MHz in the example quoted. In asynchronous pipelines the latency is therefore the sum of the individual times per stage. The pipeline may well fill up at a greater rate than its throughput and length would suggest. Furthermore not all pipeline stages require a constant processing time. For example an arithmetic logic unit (ALU) may perform an add operation much faster than a divide operation. In an asynchronous pipeline each may be treated as a single operation without slowing the general throughput to the speed of the slowest.
The article "Micropipelines", Communications of the ACM, Vol. 32, No. 6 Jun. 1989, pages 720-738 by Sutherland, I. E., describes a framework for designing asynchronous circuits. A library of circuits is described which may be used to control asynchronous pipelines which are referred to as "Micropipelines" and are event controlled, that is to say they use single electrical transitions as control signals rather than voltage levels. Communication between stages of the pipeline uses a bundled data convention. A whole data word is accompanied by a single pair of event control lines. These indicate when the data is valid and when the data has been received by the next stage in the pipeline. Event control is sometimes called transition signalling as it uses electrical transitions to convey information.
The micropipeline approach can be used to construct a microprocessor. Each element of the data-path of the microprocessor can be made to correspond to a stage of a micropipeline. This is aided by the essential hierarchical structure of micropipelines as an element of the pipeline can itself contain an arbitrary number of pipeline stages.
Micropipelines incorporate a register bank in the form of a number of registers with common sets of READ and WRITE buses. All the registers are the same width, for example in a 32 bit microprocessor they would be 32 bits wide. The microprocessor executes instructions by reading the contents of one or two of the registers out of the bank, performing some operation on the read out contents, and then writing back the result of the operation into a third register in the register bank. The number of registers read out in any instruction is limited by the number of output ports of the register bank, which is usually two. After an instruction has been issued, an instruction decoder extracts the addresses of the registers that should be read and the register to which the result of the operation identified in the instruction should be written. These register addresses are passed to the register bank so that execution of the instruction may begin. The operands are read out and passed to a processing unit such as an ALU where some operation is performed to provide the result. Some time later the result arrives back at the register bank and is written to the appropriate register. Thus, if an instruction is issued which when completed will result in data being written to a particular register, and a subsequent instruction is issued which attempts to read that particular register, the subsequent instruction must be delayed until the instruction already in progress has been completed.
The problem of delaying read instructions described above is one example of difficulties that can arise in detecting conditional information in asynchronous pipelines. In such circumstances it is usually necessary both to detect the presence of items in the pipeline and to determine the position of those items within the pipeline.